{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0187cfb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "大素数 (p): 2707\n",
      "原根/生成元 (g): 1620\n",
      "Alice's 私钥: 8706\n",
      "Bob's 私钥: 60566\n",
      "Alice's 公钥: 1183\n",
      "Bob's 公钥: 2369\n",
      "共享私钥 (Alice): 1776\n",
      "共享私钥 (Bob): 1776\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def is_prime(num):\n",
    "    if num < 2:\n",
    "        return False\n",
    "    for i in range(2, int(num**0.5) + 1):\n",
    "        if num % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def gcd(a, b):\n",
    "    while b:\n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "\n",
    "def modinv(a, b):\n",
    "    m0, x0, x1 = b, 0, 1\n",
    "    while a > 1:\n",
    "        q = a // b\n",
    "        a, b = b, a % b\n",
    "        x0, x1 = x1 - q * x0, x0\n",
    "    return x1 + m0 if x1 < 0 else x1\n",
    "\n",
    "def generate_params():\n",
    "    p = random_prime()\n",
    "    g = random.randint(2, p - 2)\n",
    "    return p, g\n",
    "\n",
    "def generate_private_key():\n",
    "    return random.randint(2, 2**16)\n",
    "\n",
    "def generate_public_key(private_key, p, g):\n",
    "    return pow(g, private_key, p)\n",
    "\n",
    "def generate_shared_secret(private_key, public_key, p):\n",
    "    return pow(public_key, private_key, p)\n",
    "\n",
    "def random_prime():\n",
    "    while True:\n",
    "        num = random.randint(10**3, 10**4)\n",
    "        if is_prime(num):\n",
    "            return num\n",
    "\n",
    "# Example\n",
    "p, g = generate_params()\n",
    "alice_private_key = generate_private_key()\n",
    "bob_private_key = generate_private_key()\n",
    "\n",
    "alice_public_key = generate_public_key(alice_private_key, p, g)\n",
    "bob_public_key = generate_public_key(bob_private_key, p, g)\n",
    "\n",
    "alice_shared_secret = generate_shared_secret(alice_private_key, bob_public_key, p)\n",
    "bob_shared_secret = generate_shared_secret(bob_private_key, alice_public_key, p)\n",
    "\n",
    "print(\"Prime number (p):\", p)\n",
    "print(\"Generator (g):\", g)\n",
    "print(\"Alice's private key:\", alice_private_key)\n",
    "print(\"Bob's private key:\", bob_private_key)\n",
    "print(\"Alice's public key:\", alice_public_key)\n",
    "print(\"Bob's public key:\", bob_public_key)\n",
    "print(\"Shared secret (Alice):\", alice_shared_secret)\n",
    "print(\"Shared secret (Bob):\", bob_shared_secret)\n",
    "\n",
    "## Output Example\n",
    "# Prime number (p): 2707\n",
    "# Generator (g): 1620\n",
    "# Alice's private key: 8706\n",
    "# Bob's private key: 60566\n",
    "# Alice's public key: 1183\n",
    "# Bob's public key: 2369\n",
    "# Shared secret (Alice): 1776\n",
    "# Shared secret (Bob): 1776\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e578d36",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
